Round Overview
Discuss this match
In this SRM both division encountered a problem set that was probably slightly on the easier side. Still, this is probably a good thing: the actual percentage of people who solved the medium problem in each division was around 50%, and there were reasonably many contestants solving all three problems.
In Division I there were no major surprises, all the top spots were claimed by some of the “big guns”. The victory went to UdH-WiNGeR. The fastest time on the hard problem and three successful challenges gave him quite a comfortable lead of more than 200 points in front of the second Petr. Third place went to neal_wu.
The top spot in Division II was claimed by ahxun2006. The best of the newcomers was nehzilrz, who placed 23rd.
OnTheFarmDivTwo
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 556 / 605 (91.90%) |
Success Rate | 395 / 556 (71.04%) |
High Score | AcceptCrazy for 249.80 points (0 mins 48 secs) |
Average Score | 208.38 (for 395 correct submissions) |
Let A be the number of chickens and B the number of cows in the yard. Then the number of heads is A+B and the number of legs is 2A+4B.
Given A and B, computing A+B and 2A+4B is easy. In this task we are interested in computing it the other way round: we are given the values H=A+B and L=2A+4B, and our goal is to determine A and B.
This is simply a set of two linear equations. In real numbers it always has a unique solution. How to solve it? For example, from the first equation we get that 2H=2A+2B. If we now subtract this from the second equation, we get that L-2H=2B, hence B=(L-2H)/2. And then from the original first equation we get A=H-B=(4H-L)/2. Once you compute A and B using the formulas, you need to check whether they are indeed non-negative integers.
The number of legs on a chicken is even, and so is the number of cow’s legs. Hence if the total is odd, we know that there is no answer.
Moreover, suppose there are H heads. As each animal has at least two legs, you must have at least 2H legs in total. Similarly, you cannot have more than 4H legs.
And actually, each even value between 2H and 4H is reachable. For example, suppose that we want to produce 2H+8 legs. We can start with taking H chickens, so that we have 2H legs. Now note that whenever we swap a chicken for a cow, the number of legs grows by two. So in our example we need to do this exactly four times.
A generalization of this approach gives you exactly the formulas from the previous solution.
If there are at most 1,000,000 heads, there have to be at most 1,000,000 chickens. We can write a loop that will try out all possible values for the number of chickens. For each of them, use the number of heads to determine the number of cows, and then check whether the number of legs matches your current number of chickens and cows.
SequenceOfCommands
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 399 / 605 (65.95%) |
Success Rate | 205 / 399 (51.38%) |
High Score | tgudlek for 463.51 points (8 mins 5 secs) |
Average Score | 308.90 (for 205 correct submissions) |
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 467 / 471 (99.15%) |
Success Rate | 365 / 467 (78.16%) |
High Score | bbi5291 for 248.17 points (2 mins 26 secs) |
Average Score | 211.21 (for 365 correct submissions) |
When reading the problem statement for the first time, the task may be a little scary: An infinite sequence of commands? How do I simulate that? And some circles?
However, once we start playing around with the task, we’ll discover that there is nothing to be afraid of. A good first step is to actually read through all the examples and simulate them by hand to see what happens.
How to approach the problem? Certainly we can not simulate the sequence of commands an infinite number of times. However, we don’t actually need to do that: it’s the same short sequence over and over again! If we simulate it once, we’ll know its total effect, and this will keep on repeating forever.
Once you start trying out some sequences and trying what happens, you should quicky realize that there are three somehow different cases.
After executing the sequence once, you’ll end up in the place where you started, rotated in the same direction.
After executing the sequence once, you’ll end up in some other place, rotated in the same direction.
After executing the sequence once, you’ll end up rotated in some other direction.
In the first case your infinite path is clearly bounded: you will run in a loop along the same course forever. Similarly, in the second case your infinite path is clearly unbounded: if your starting point is (0,0) and your final point is (x,y), then after executing the sequence k times you’ll end up at (kx,ky). So clearly you can get arbitrarily far from your starting point.
Now let’s take a look at the last case. First of all, consider the situation when after executing the sequence for the first time you end at (x,y) rotated in the opposite direction. What will happen when you execute the same sequence for the second time? As you are now rotated by 180 degrees, its effect will be opposite: you’ll move by (-x,-y). The total number of rotations is the same as before, hence you’ll again end up rotated by 180 degrees. In other words, you will return exactly to the same state in which you started: we are back at (0,0) and rotated in the same direction. Hence the infinite path is necessarily cyclic, and therefore bounded.
And a similar thing happens if the original sequence just rotates you by 90 degrees. Executing this sequence twice will rotate you by 180 degrees. And we already saw what happens next: Executing the same thing again (i.e., executing the original sequence two more times) will get you back to the starting point.
Once you got this far, there were two possible ways how to implement this solution. In the first way, you simulate the given sequence once, find out which of the three cases occured and give the correct output. In the second approach, which is a little bit simpler, you just execute the input sequence four times. Now you can be sure that your final direction is the same you started with, hence there are just two cases: if you are back at (0,0), the sequence is bounded, otherwise it’s not.
ChildlessNumbers
Problem Details
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 176 / 605 (29.09%) |
Success Rate | 47 / 176 (26.70%) |
High Score | AcceptCrazy for 995.82 points (1 mins 50 secs) |
Average Score | 632.70 (for 47 correct submissions) |
To solve this problem, one tricky observation was necessary, which is why this problem was correctly classified as a Division 2 hard.
When looking at the constraints, you could note that the range of values we need to process is pretty short. One thing that could help us would be a fast way how to tell whether a number is childless or not. If we knew how to do this, we would be done: for each number in the given range we would check whether it is childless, and in case it is, we would increment a counter.
Okay, but can we do that?
To prove that a number Y is not childless, all we need to do is to find one child. That is, we are looking for a number X such that X / D(X) = Y. Recall that D(X) is the sum of digits of X.
Now we can note that any such X must be an integer multiple of our Y. One possible way how to start looking for that X would be to consider all multiples of Y and to check whether they work. When we are testing whether X=kY is a child of Y, all we need to verify is whether the digit sum matches, i.e., whether D(kY) = X / Y = k.
This is all nice, but when can we stop and conclude that there is no good X? Below we will show that it is sufficient to consider just a few small multiples of Y. If there is no child among them, there is no child at all.
The resulting algorithm can be implemented in a few lines: For each Y between A and B inclusive, we try the first 108 multiples of Y. If none of them is a child of Y, we conclude that Y is childless.
We will now prove that we just need to consider the first few multiples of Y. Now comes the tricky observation: when X grows, the largest possible D(X) grows as well - but at a much much smaller rate. Imagine a really huge X with 100 digits. Then D(X) is still surely at most 900: we have 100 digits, and each of them is at most a nine. Hence X / D(X) is still very huge: it will surely have at least 97 digits, which is clearly way larger than our Y.
Let’s try to generalize the above observation to a proper argument. We know that our Y is at most 109. What we want to find out is some bound on the multiple of Y we need to consider. In other words, we want to find some k such that X=kY is provably too large.
Take any k. We are looking for a number X that has two properties at the same time. First, we must have X/k = Y, and second, the digit sum of X must be exactly k. What’s the smallest number of digits X needs to have in order to satisfy the second property? The answer is t=ceil(k/9), that is, the smallest integer that is ≥k/9. Any number with less than t digits has the digit sum at most 9(t-1), which is less than k.
Now, if X has at least t digits, we know that X ≥ 10t-1. Now what about the value X / k? We know that X is at least 10t-1, k is at most 9t, hence X / k is at least 10t-1/(9t).
If we now take any k > 108=9*12, we get t ≥ 13. And for any such t the smallest possible value of X / k already exceeds 109. (Clearly f(t) = 10t-1/(9t) is an increasing function, and already for t=13 it is clearly too large.) On the other hand, we are only interested in Y ≤ 109. This means that for any valid Y the largest value of k we have to consider is 108.
Final note #1: For Y up to 109 the bound we just proved is not tight, but it is pretty close. The actual largest value needed is 93. The smallest case where it is needed: for Y=860,202,043 the smallest child is X=93*Y.
Final note #2: The official name for childless numbers is inconsummate numbers.
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 382 / 471 (81.10%) |
Success Rate | 197 / 382 (51.57%) |
High Score | 7ania7 for 467.27 points (7 mins 37 secs) |
Average Score | 315.03 (for 197 correct submissions) |
This problem consisted of two independent parts. First we need to generate the red points, then we need to compute the number of right triangles they determine.
To count the right triangles, all the insight we need is the Thales’ theorem. Three points on a circle form a right triangle if and only if two of the three red points are directly opposite each other. Thus to count all the right triangles, we have a really simple algorithm: for each of the N red points, we check whether we have a point in the exactly opposite position. If yes, each of the remaining N-2 points forms a right triangle with our pair of points. In this way, we’ll process all points in linear time, and during this process we’ll count each right triangle exactly twice (or exactly once, if we stop after processing one half of the circle).
This leaves us with the question how to generate the points. Just following the naive approach described in the problem statement was not sufficient. For example, consider a formula that would try to place all red points onto the same location. If you were simulating this one by one, and always use linear search to look for the next free location, the total number of steps will be quadratic in the number of points.
One possible improvement was to do the generation using a better data structure. The maximum bound on the number of places was intentionally low so that almost any reasonable data structure with operations in logarithmic time could be easily tweaked to work. For example, in C++ you could have a set with all the empty places and use lower_bound to find the right one for your next red point. If you wanted to, you could implement your own interval tree (or equivalently a Fenwick tree) with the same functionality.
However, there is also a simpler approach that is both faster and easier to code. You can do the generation in two phases. First you generate all the red points in the places where the formula wants them. Of course, once this phase terminates, there can be places that contain more than one red point. However, we can now easily fix this: We’ll just walk along the cycle. Each time we encounter a place with more than one red point, we pick up all but one of them. And each time we encounter an empty place, if we are currently carrying some red points, we drop one of them. It is easily seen that this process actually produces the correct distribution of red points, and that regardless of where we start, walking two full circles is sufficient for the process to terminate.
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 49 / 471 (10.40%) |
Success Rate | 20 / 49 (40.82%) |
High Score | UdH-WiNGeR for 793.99 points (15 mins 19 secs) |
Average Score | 498.73 (for 20 correct submissions) |
This is a pure combinatorial problem. We are counting some valid arrangements, and there’s an awful lot of them. Which means that we cannot count them one at a time. We have to look for some patterns and use them to count the arrangements more efficiently.
Imagine one arbitrary valid arrangement. As the arrangement is valid, no row and no column may contain rooks of two different colors. Some of the rows and columns may be completely empty, and each of the others only contains rooks of one specific color.
Label each row and each column using the color of the rooks in it. Now remove all the rooks and just keep the labels. What happens if you now try to reconstruct one valid arrangement?
Many of the cells must be left empty. For example, all cells in rows and columns that are marked as empty have to remain empty. But that’s not all! Even all the cells where the row and column labels differ have to remain empty. For example, if you have a cell in a red row and a blue column, there is no color you can place on this cell. In other words, you can only place a rook of color X onto a cell such that both its row label and column label is X.
This actually splits the problem into Z separate subproblems, one per each of the Z colors. If we are given the row and column labels, we can place rooks of each color separately. The total number of arrangements that correspond to the given labels can be computed as a product of the numbers of arrangements for each of the colors.
At many places in this solution we will use the binomial coefficients. We will denote them comb(x,y). That is, comb(x,y) is the number of ways in which you can pick y elements out of x. These values satisfy the well-known recurrence: comb(x,0)=comb(x,x)=1, and comb(x,y)=comb(x-1,y-1)+comb(x-1,y). The largest x we’ll ever need is equal to the area of the chessboard. Using the recurrence, these values can easily be precomputed in the beginning and stored in a 2D array. Note that for y<0 and y>x we have comb(x,y)=0.
The single color subproblem we now encountered looks as follows: given the dimensions R×C of a rectangle and the number N of rooks, what is the number S(R,C,N) of ways in which the N rooks can be placed into the rectangle, given that each row and each column must contain at least one rook? There are multiple possible approaches to computing S(R,C,N), we will now show two of them.
The first option is to use the inclusion and exclusion principle.
Clearly, if we are placing N rooks on a R×C board without any constraints, the number of possibilities is comb(RC,N). Now let U(R,C,N) be the number of ways how to place the rooks in such a way that no column is empty. (Rows are allowed to be empty.) The value U(R,C,N) can be computed using inclusion and exclusion as follows: We take all the comb(RC,N) arrangements. For each column, we subtract the comb(R(C-1),N) arrangements in which this column is empty. For each pair of columns we now add the comb(R(C-2),N) arrangements in which both are empty, and so on. This gives us the following formula:
U(R,C,N) = sum(i=0…C) (-1)i * comb(C,i) * comb(R(C-i),N).
Now we can use the values U to compute the answer S(R,C,N) we are actually interested in. The idea will be the same: we use inclusion and exclusion again, but this time on rows. The final formula looks as follows:
S(R,C,N) = sum(i=0…R) (-1)i * comb(R,i) * U(R-i,C,N).
We will now show a different approach for the single color subproblem. We will use dynamic programming. The subproblems will have the following form: given the number R’ of remaining rows, the number N’ of remaining rooks, and the number C’ of columns that still need to get at least one rook, what is the number of valid arrangements?
For fixed C, let A(r,n,c) be the answer to the subproblem defined above. We now want to formulate a recurrence that will allow us to compute all of these answers efficiently. Let’s consider all possible ways how to fill the next row. Each of those will give us one subproblem with r-1 rows. Now let’s count these ways efficiently. Assume that we place c1 rooks into columns that already had a rook and c2 rooks into columns that did not have any rooks yet.Each such placement will produce a new subproblem with r-1 rows, n-c1-c2 rooks, and c-c2 empty columns.
Therefore we get the following formula:
A(r,n,c) = - A(r-1,n,c) + sum(c1=0…C-c) sum(c2=0…c) comb(C-c,c1) * comb(c,c2) * A(r-1,n-c1-c2,c-c2)
(The term in front of the sum just means that when computing the sum we skip the case c1=c2=0, as we need to place at least one rook into each row. We can get rid of the two nested sums if we also memoize in the middle, i.e., after placing rooks into the non-empty columns.)
Now that we know how to solve the single color version, we can get back to solving the original problem. We will use one more “layer” of dynamic programming. The subproblems in this case will be: given just the rooks of the first Z’ colors and a submatrix of dimensions R’×C’, what is the number of valid arrangements?
Let B(z,r,c) be the answer to this subproblem. The recurrence relation is simple: for color z, we try all possible values for the number of rows and columns this color gets. Each time we multiply the number of arrangements for the remaining colors and the number of arrangements for this single color within the selected rectangle:
B(z,r,c) = sum(r1=1…r) sum(c1=1…c) comb(r,r1) * comb(c,c1) * S(r1,c1,counts[z]) * B(z-1,r-r1,c-c1)
The constraints for this problem were intentionally pretty low so that many different DP approaches could work in time. It is actually possible to solve the problem with the usual TopCoder constraints: 50 rows, 50 columns, and 50 rook colors. Consider it an additional challenge :)